package day317;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author tmh
 * @date 2023/3/17 17:04
 * @description
 */
public class T15 {
    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        threeSum(nums);
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //判断这个数组是否是空的或者这个数组是否存在三个元素，如果存在，那么就直接不需要额外判断了
        if (nums == null || nums.length < 3) {
            return result;
        }
        //对这个数组进行排序
        Arrays.sort(nums);
        //开始遍历这个数组
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            //如果遍历开始的其实元素都大于零了，直接退出去了
            //如果排序后的一个数字都大于0了，那么三个数之后肯定也都是大于零了
            if (nums[i] > 0) {
                break;
            }
            //然后去重，当起始的值等于前面一个元素的时候，那么得到的结果将会和前面一次相同
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //把满足要求的数据放在result里面
            int l = i + 1;
            int r = length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //去重，在将左指针和右指针移动的时候，先对左右指针的值进行判断
                    //如果重复，直接跳过
                    //去重，因为i不变，当此时l取得的数值和后一个数相同，直接就是跳过
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    //去重，因为i不变，当r取得的值和前面一个相同的时候，也是跳过去
                    while (l < r && nums[r] == nums[r - 1]) {
                        r--;
                    }
                    //将左指针右移，右指针左移,这个时候移动的是l和r的位置，i的位置并没有进行变换,即就是满足了条件，两个指针都要移动
                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;
                } else if (sum > 0) {
                    r--;
                }
            }
        }
        return result;
    }
}
